package org.labuladong.暴力搜索算法.回溯算法;

import java.util.Scanner;

/**
 * @Author: qingle
 * @Date: 2024/10/28-16:11
 * @Description: 0-1 背包问题
 * @version: 1.0
 */
public class LC_01_背包问题 {

	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int W = scanner.nextInt();
		scanner.nextLine();
		int[] wt = new int[N];
		for (int i = 0; i < N; i++) {
			wt[i] = scanner.nextInt();
		}
		scanner.nextLine();
		int[] val = new int[N];
		for (int i = 0; i < N; i++) {
			val[i] = scanner.nextInt();
		}
		int ans = knapsack(W, N, wt, val);
		System.out.println(ans);
	}

	static int knapsack(int W, int N, int[] wt, int[] val) {
		// base case 已初始化
		int[][] dp = new int[N + 1][W + 1];
		for (int i = 1; i <= N; i++) {
			for (int w = 1; w <= W; w++) {
				if (w - wt[i - 1] < 0) {
					// 这种情况下只能选择不装⼊背包
					dp[i][w] = dp[i - 1][w];
				} else {
					// 装⼊或者不装⼊背包，择优
					dp[i][w] = Math.max(
						dp[i - 1][w - wt[i-1]] + val[i-1],
						dp[i - 1][w]
					);
				}
			}
		}
		return dp[N][W];
	}
}
